package main

import "fmt"

func main() {
	r := candy([]int{1, 0, 2})
	fmt.Println(r)
}

/**
https://leetcode-cn.com/problems/candy/submissions/

解析:
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html#%E6%80%9D%E8%B7%AF
*/

//func candy(ratings []int) int {
//	l := len(ratings)
//	if l == 0 {
//		return 0
//	}
//	if l == 1 {
//		return 1
//	}
//	left := make([]int, l)
//	for k, _ := range left { // 每个孩子至少一个糖果
//		left[k] = 1
//	}
//	right := make([]int, l)
//	copy(right, left)
//
//	//左规则: 每个孩子i和他的左侧i-1满足 如果i的评分大于i-1，那么i的糖果数大于i-1
//	for i := 1; i < l; i++ {
//		if ratings[i] > ratings[i-1] {
//			left[i] = left[i-1] + 1
//		}
//	}
//
//	//右规则: 每个孩子i和他的右侧+1满足 如果i的评分大于i+1，那么i的糖果数大于i+1
//	for i := l - 2; i >= 0; i-- {
//		if ratings[i] > ratings[i+1] {
//			right[i] = right[i+1] + 1
//		}
//	}
//
//	count := 0
//	for i := 0; i < l; i++ {
//		count += max(left[i], right[i]) // 取既满足左规则、又满足右规则的数量
//	}
//	return count
//
//	return count
//}

// 优质解法
func candy(ratings []int) int {
	l := len(ratings)
	m := make([]int, l)
	for k := range m {
		m[k] = 1
	}

	for i := 1; i < l; i++ {
		if m[i] > m[i-1] {
			m[i] = m[i-1] + 1
		}
	}

	for i := l - 2; i >= 0; i-- {
		if m[i] > m[i+1] {
			m[i] = max(m[i], m[i+1]+1)
		}
	}

	count := 0
	for i := 0; i < l; i++ {
		count += m[i]
	}

	return count
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
